package edu.cityu.cs.hk.datastructures;

//begin#fragment NodeSequence
/** Implementation of a sequence by means of a doubly linked list. */
public class NodeSequence extends NodeList implements Sequence {
  /** Checks whether the given rank is in the range [0, n - 1] */
  protected void checkRank(int r, int n) 
    throws BoundaryViolationException {
    if (r < 0 || r >= n)
      throw new BoundaryViolationException("Illegal rank: " + r);
  }
  /** Returns the position containing the element at the given rank;
   * O(n) time. */
  public Position atRank (int rank) {
    DNode node;
    checkRank(rank, size());
    if (rank <= size()/2) { // scan forward from the head
      node = header.getNext();
      for (int i=0; i < rank; i++)
	node = node.getNext();
    }
    else { // scan backward from the tail
      node = trailer.getPrev(); 
      for (int i=1; i < size()-rank; i++)
	node = node.getPrev();
    }
    return node;
  }
//end#fragment NodeSequence
  /** Returns the rank of the element stored at the given position;
   * O(n) time. */
  public int rankOf(Position p)
      throws InvalidPositionException {
    DNode query = checkPosition(p);
    DNode node = (DNode) first();
    for (int i = 0; node != trailer; i++, node = node.getNext()) 
      if (query == node) return i;
    throw new InvalidPositionException("Position not found.");
  }
  /** Returns the element stored at the given rank; O(n) time */
  public Object elemAtRank (int rank)
      throws BoundaryViolationException {
    checkRank(rank, size());
    return atRank(rank).element();
  }
//begin#fragment NodeSequence
  /** Inserts an element at the given rank; O(n) time. */
  public void insertAtRank (int rank, Object element)
    throws BoundaryViolationException {
    checkRank(rank, size() + 1);
    if (rank == size())
      insertLast(element);
    else {
      insertBefore(atRank(rank), element);
      }
  }
  /** Removes the element stored at the given rank; O(n) time. */
  public Object removeAtRank (int rank)
    throws BoundaryViolationException {
    checkRank(rank, size());
    return remove(atRank(rank));
  }
//end#fragment NodeSequence
  /** Replaces the element stored at the given rank; O(n) time. */
  public Object replaceAtRank (int rank, Object element) 
      throws BoundaryViolationException {
    checkRank(rank, size());
    return replace(atRank(rank),element);
  }
}
